import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 25397
 * Date: 2022-01-23
 * Time: 19:01
 */
public class TestSort {
    //插入排序
    //时间复杂度：O(N^2)——最坏情况，该排序最好情况是O（N）——本身就是有序的，但我们说一般都是最坏情况
    //空间复杂度：O(1)
    //稳定性：稳定的
    //ps:本身稳定的排序可以变成不稳定的，但本身不稳定的不能变成稳定的
    public void insertSort(int[]array){
        for(int i=1;i<array.length;i++){
            int tmp=array[i];
            int j=0;
            for(j=i-1;j>=0;j--){
                if(array[j]>tmp){
                    array[j+1]=array[j];
                }else{
                    array[j+1]=tmp;//只要j回退的时候，遇到了比tmp小的元素就结束
                    break;
                }
            }

            //j回退到了小于0的地方
            array[j+1]=tmp;
        }
    }



    //希尔排序
    //将众多数据，分成若干组，每组进行插入排序

    //如有10000个数据，对这组直接进行插入排序
    //时间复杂度为：10000*10000=1亿

    //如果将这1w个数据分100组，每组100数据
    //每组插入排序时间复杂度为100*100
    //共100组，总计100*100*100=100 0000
    //再缩小组数，比如组数50，继续对这50组排序，—排序速度越来越快，前面100组已经趋于有序了
    //以此类推，一直到组数为1——排序速度越来越快
    //注意！最后以此排序必须是整体看成1组，也就是10000个数据算一组，但由于前面预排序很多次
    //我们最后以此排序会非常快

    //但直到现在，没有人研究出来最好前面预排序要排多少次——我们自己设计即可

    //这种就是希尔排序
    //时间复杂度O（n^1.3-n^1.5)——由于预排序次数每个人设计不同，只能保证是在这个范围内
    //希尔排序是不稳定的

    //ps:怎么快速判断是否稳定——看是否发生了跳跃式交换，如果发生了，就是不稳定的
    public static void shell(int[]array,int gap){
        for(int i=1;i<array.length;i++){
            int tmp=array[i];
            int j=0;
            for(j=i-gap;j>=0;j-=gap){
                if(array[j]>tmp){
                    array[j+gap]=array[j];
                }else{
                    break;
                }
            }

            //j回退到了小于0的地方
            array[j+gap]=tmp;
        }
    }

    public static void shellSort(int[]array){
        int gap= array.length;//gap用于标记预排序组数
        while(gap>1){
            shell(array,gap);
            gap/=2;
        }
        shell(array,1);//保证最后一组是1
    }

    /*public static void main(String[] args) {
        int[]arr={12,5,9,34,6,8,33,56,89,0,7,4,22,55,77};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
        //打印[0, 4, 5, 6, 7, 8, 9, 12, 22, 33, 34, 55, 56, 77, 89]
    }*/



    public static void swap(int[]arr,int i,int j){
        int tmp=0;
        if(arr[j]<arr[i]){
            tmp=arr[j];
            arr[j]=arr[i];
            arr[i]=tmp;
        }
    }

    //选择排序
    public static void selectSort(int[] arr){
        for(int i=0;i< arr.length;i++){
            for(int j=i+1;j< arr.length;j++){
                swap(arr,i,j);
            }
        }
    }
    //优化版选择排序
    public static void selectSort2(int[]arr){
        for(int i=0;i< arr.length;i++){
            int minIndex=i;//用于标记最小值下标
            for(int j=i+1;j< arr.length;j++){
                if(arr[j]<arr[minIndex]){
                    minIndex=j;
                }
            }
            swap(arr,i,minIndex);
        }
    }

    //两个方法时间复杂度都是O（N）
    /*public static void main(String[] args) {
        int[]arr={12,5,9,34,6,8,33,56,89,0,7,4,22,55,77};
        //selectSort(arr);
        //System.out.println(Arrays.toString(arr));
        //[0, 4, 5, 6, 7, 8, 9, 12, 22, 33, 34, 55, 56, 77, 89]

        selectSort2(arr);
        System.out.println(Arrays.toString(arr));
        //[0, 4, 5, 6, 7, 8, 9, 12, 22, 33, 34, 55, 56, 77, 89]
    }*/

    //堆排序
    //排序原理和选择排序一样，
    //只是不再使用遍历的方式查找无序区间最大的数，二是通过堆来选择无序区间的最大数
    //注意：排升序建大堆，排降序建小堆
    //这里以大堆为例
    //时间复杂度O（n*log2 n），空间复杂度O（1）
    //稳定性：不稳定
    public static void heapSort(int[] arr){
        //1.建队——时间复杂度O（n）
        createHeap(arr);
        int end= arr.length-1;
        //2.交换，调整——时间复杂度O（n*log2 n），log以2为底的n
        while(end>0){
            swap(arr,0,end);
            shiftDown(arr,0,end);
            end--;
        }
    }

    public static void createHeap(int[] arr){
        for(int parent=(arr.length-1-1)/2;parent>=0;parent--){
            //arr.length-1是最后一个元素下标
            //(arr.length-1-1)/2 是已知孩子节点，求双亲节点公式
            shiftDown(arr,parent, arr.length);
        }
    }

    public static void shiftDown(int []arr,int parent,int len){
        int child=2*parent+1;//左孩子
        while(child<len){
            if(child+1<len&&arr[child]<arr[child+1]){
                //child+1<len是没有遍历完
                //arr[child]<arr[child+1]是左孩子小于右孩子
                child++;//保证是最大的孩子
            }
            if(arr[child]>arr[parent]){
                swap(arr, child, parent);
                parent=child;
                child=2*parent+1;
            }else{
                break;
            }
        }
    }

    /*public static void main(String[] args) {
        int[]arr={12,5,9,34,6,8,33,56,89,0,7,4,22,55,77};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
        //[0, 4, 5, 6, 7, 8, 9, 12, 22, 33, 34, 55, 56, 77, 89]
    }*/


    //冒泡排序
    //时间复杂度：O（n^2)
    //空间复杂度：O（1）
    //稳定性：稳定
    public static void bubbleSort(int[]array){
        for(int i=0;i<array.length;i++){
            boolean flg=false;//优化：这里可能在某一趟就有序了，后面就没必要走了
            for(int j=0;j<array.length-1-i;j++){
                //这里array.length必须要-1，因为下面有一个j+1,下标不能等于长度,否则数组越界
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flg=true;//如果一次没有进来，说明就是有序的了
                }
            }
            if(flg==false){
                break;
            }
        }
    }

    /*public static void main(String[] args) {
        int[]arr={12,5,9,34,6,8,33,56,89,0,7,4,22,55,77};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
        //[0, 4, 5, 6, 7, 8, 9, 12, 22, 33, 34, 55, 56, 77, 89]
    }*/



    //快速排序-非常重要！！！
    //时间复杂度：O（n*log2n），log2n表示log以2为底的n
    //空间复杂度：O（logn）
    //稳定性：不稳定
    public static void quickSort(int[]array){
        //这里是为了接口统一，读者也可以直接用里面的quick
        quick(array,0, array.length-1);
    }

    public static void quick(int[]arr,int left,int right){
        if(left>=right){
            return;
        }
        int pivot=partition(arr,left,right);//找基准
        quick(arr,left,pivot-1);//递归基准坐边
        quick(arr, pivot+1, right);//递归基准右边
        //找基准类似一棵二叉树
    }
    private static int partition(int[]arr,int start,int end){
        //找基准，挖坑法
        int tmp=arr[start];
        while(start<end){
            while(start<end&&arr[end]>=tmp){
                //为什么多加一个start<end?
                //防止出现1234这种序列，tmp=1,arr[tmp]>=tmp一直成立,end一直--，最后越界访问到arr[-1]
                end--;
            }
            //end下标遇到了<tmp的值
            arr[start]=arr[end];
            while(start<end&&arr[start]<=tmp){
                //为什么多加一个start<end?
                //防止出现4321这种序列，tmp=4,arr[start]<=4一直成立，start一直++,最后越界访问到arr[arr.length]
                start++;
            }
            //start下标遇到了>tmp的值
            arr[end]=arr[start];
        }
        arr[start]=tmp;
        //相遇位置就是基准位置
        return start;//这里start和end一样，return end也可以
    }
    /*public static void main(String[] args) {
        int[]arr={6,1,2,7,9,3,4,5,10,8};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
        //[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    }*/




    //归并排序-重要
    //时间复杂度：O(N+logN)
    //空间复杂度：O(N)
    //稳定性：稳定
    //ps:学过的只有3个稳定排序——冒泡，插入，归并

    //铺垫：
    //给两个有序数组（有序指从小到大），让你合成一个有序数组
    public static int[] mergeArray(int []arr1,int[]arr2){
        int s1=0;
        int s2=0;
        int e1=arr1.length-1;
        int e2=arr2.length-1;
        int[] arr3=new int[arr1.length+arr2.length];//新数组长度是两数组长度和
        int bj1=0;//用于标记数组1是否是先遍历完的
        int bj2=0;//用于标记数组2是否是先遍历完的
        int i=0;//用于标记数组3下标
        while(s1<=e1&&s2<=e2){
            if(arr1[s1]<=arr2[s2]){
                arr3[i]=arr1[s1];
                s1++;
                if(s1>e1){//说明是数组1先遍历完的
                    bj1=1;
                }
            }else{
                arr3[i]=arr2[s2];
                s2++;
                if (s2>e2){//说明是数组2先遍历完的
                    bj2=1;
                }
            }
            i++;
        }
        if(bj1==1){//数组1先遍历完了，后面直接往数组3里面放数组2剩下元素即可
            while(s2<=e2){
                arr3[i++]=arr2[s2++];
            }
        }
        if(bj2==1){//数组2先遍历完了，后面直接往数组3里面放数组1剩下元素即可
            while(s1<=e1){
                arr3[i++]=arr1[s1++];
            }
        }
        return arr3;
    }

    /*public static void main(String[] args) {
        int []arr1={1,6,7,10,11};
        int []arr2={0,2,3,4,9};
        int []arr3=mergeArray(arr1,arr2);
        System.out.println(Arrays.toString(arr3));
        //[0,1, 2, 3, 4, 6, 7, 9, 10,11]
    }*/

    //完整归并排序：
    //如何将一个无规律的数组，转换成2个有序数组
    public static void mergeSort(int []arr){
        mergeSortInternal(arr,0,arr.length-1);
    }

    private static void mergeSortInternal(int []arr,int low,int high){
        if(low>=high){//判断条件，既是开始也是结束
            return;
        }
        int mid=(low+high)/2;//看起来高端一点的写法：（low+high)>>>1，表示无符号右移1位，效果和除2一样
        //得到mid后，分别递归数组的左边和右边
        mergeSortInternal(arr,low,mid);
        //该行代码走完，说明整个左边递归结束
        mergeSortInternal(arr,mid+1,high);
        //该行代码走完，说明整个右边递归结束
        //左右都递归结束，也就是说：整个数组被分解为1个1个的数字
        //下面进行有序的归并
        merge(arr,low,mid,high);

    }

    private static void merge(int []arr,int low,int mid,int high){
        int s1=low;
        int e1=mid;
        int s2=mid+1;
        int e2=high;
        int []arr3=new int[high-low+1];//新数组长度是两数组长度和
        int i=0;//用于标记数组3下标
        while(s1<=e1&&s2<=e2){
            if(arr[s1]<=arr[s2]){
                arr3[i++]=arr[s1++];

            }else{
                arr3[i++]=arr[s2++];
            }
        }
        //数组1先遍历完的情况，后面直接往数组3里面放数组2剩下元素即可
        while(s2<=e2){
            arr3[i++]=arr[s2++];
        }
        //数组2先遍历完的情况，后面直接往数组3里面放数组1剩下元素即可
        while(s1<=e1){
            arr3[i++]=arr[s1++];
        }


        //拷贝arr3数组内的元素，放入原来的数组arr中
        for( int j=0;j<i;j++){
            arr[j+low]=arr3[j];//这里为什么要加low?
            //比如两组组数据：1 2 3 4    5 6 7 8

            //合并后应该是8个数字为1组
            //下标分别为：  0 1 2 3    4 5 6 7

            //第一组low是0，你1就放在0号位
            //第二组low是4，你5就放在4号位
            //如果你i不加low，第二组数据就会把第一组数据覆盖掉
        }
    }
    /*public static void main(String[] args) {
        int []arr={12,5,9,34,6,0,33,56,89,0,7,4,0,55,77};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
        //[0, 0, 0, 4, 5, 6, 7, 9, 12, 33, 34, 55, 56, 77, 89]
    }*/



    //非递归方法实现——归并排序
    public static void mergeSort2(int[]arr){
        int num=1;//每组数据个数
        while(num<arr.length){
            //每组1个元素的时候，i要遍历1次
            //每组2个元素的时候，i要遍历1次
            //...
            for(int i=0;i<arr.length;i+=num*2){
                int left=i;
                int mid=left+num-1;//mid有可能会越界
                if(mid>=arr.length){
                    mid=arr.length-1;
                }
                int right=mid+num;
                if(right>=arr.length){
                    right=arr.length-1;
                }
                //下标确定后，进行合并
                merge(arr,left,mid,right);
            }
            num*=2;
        }
    }
    /*public static void main(String[] args) {
        int []arr={12,5,9,34,6,0,33,56,89,0,7,4,0,55,77};
        mergeSort2(arr);
        System.out.println(Arrays.toString(arr));
        //[0, 0, 0, 4, 5, 6, 7, 9, 12, 33, 34, 55, 56, 77, 89]
    }*/


    //计数排序
    //适用于有n个数，且数据范围为0~n之间
    //时间复杂度O（N）
    //空间复杂度O(M),M:表示当前数据范围，比如900-999，M是100
    //稳定性：不稳定
    public static void countingSort(int[]arr){
        int maxVal=arr[0];
        int minVal=arr[0];
        for(int i=0;i<arr.length;i++){
            if(arr[i]<minVal){
                minVal=arr[i];
            }
            if(arr[i]>maxVal){
                maxVal=arr[i];
            }
        }
        //for走完，最大值最小值就确定了
        int[]count=new int[maxVal-minVal+1];//确认计数数组长度,比如最小值0，最大值10，长度为11
        for(int i=0;i<arr.length;i++){
            int index=arr[i];
            count[index-minVal]++;//这里为什么要-minVal?
            //比如我的数组大小是100，但是要存数值大小是900-999的数
            //我们-900，让900-999的每个数与数组下标0-99对应
        }
        //到这里，在计数数组中，已经把array数组，每个数据出现的次数计算好了
        //接下来，只需要遍历计数数组，把数据写回array
        int indexArr=0;
        for(int i=0;i< count.length;i++){
            while(count[i]>0){
                //这里要加上minVal（你之前减过1次，再加上才是真实值）
                arr[indexArr]=i+minVal;
                count[i]--;//放一个值，当前存放的计数的值要--一次
                indexArr++;//下标往后移动
            }
        }
    }
    public static void main(String[] args) {
        int []arr={12,5,9,34,6,0,33,56,89,0,7,4,0,55,77};
        countingSort(arr);
        System.out.println(Arrays.toString(arr));
        //[0, 0, 0, 4, 5, 6, 7, 9, 12, 33, 34, 55, 56, 77, 89]
    }
}
